package graph;

import linearList.LinkedList;
import linearList.SeqList;
import queue.LinkedQueue;
import queue.Queue;
import queue.SeqQueue;

// 邻接矩阵表示的带权图类
public class MatrixGraph<T> {
    // 最大权值，表示无穷大
    public static final int MAX_WEIGHT = 0x0000ffff;

    private SeqList<T> vertexList;
    private int[][] matrix;

    public static void main(String[] args) {
        testG3();
        testG4();
    }

    private static void testG4() {
        String[] vertices = {"A", "B", "C", "D", "E"};
        Triple edges[] = {new Triple(0,1,10), new Triple(0,3,30), new Triple(0,4,99),
                new Triple(1,2,50), new Triple(1,3,40),
                new Triple(2,4,10),
                new Triple(3,2,20), new Triple(3,4,60),
        };
        MatrixGraph<String> graph = new MatrixGraph<>(vertices, edges);

        System.out.println();
        System.out.println("深度优先遍历连通无向图G4:");
        for (int i = 0; i < graph.vertexCount(); i++)
            graph.DFSTraverse(i);

        System.out.println("广度优先遍历连通无向图G4:");
        for (int i = 0 ; i < graph.vertexCount() ; i++)
            graph.BFSTraverse(i);
    }

    private static void testG3() {
        /**
         *      带权无向图 (A,B,C,D,E)
         *
         *      0    45    28    10     ∞
         *     45     0    12     ∞    21
         *     28    12     0    17    26
         *     10     ∞    17     0    15
         *      ∞    21    26    15     0
         */
        String[] vertices = {"A", "B", "C", "D", "E"};
        Triple[] edges = {new Triple(0, 1, 45), new Triple(0, 2, 28), new Triple(0, 3, 10),
                new Triple(1, 0, 45), new Triple(1, 2, 12), new Triple(1, 4, 21),
                new Triple(2, 0, 28), new Triple(2, 1, 12), new Triple(2, 3, 17)
                ,new Triple(2,4,26),
                new Triple(3, 0, 10), new Triple(3, 2, 17), new Triple(3, 4, 15),
                new Triple(4, 1, 21), new Triple(4, 2, 26), new Triple(4, 3, 15)
        };
        MatrixGraph<String> graph = new MatrixGraph<>(vertices, edges);
        System.out.println("带权无向图G1，" + graph.toString());


        /**
         *      0    45    28    10     ∞      ∞
         *     45     0    12     ∞    21      ∞
         *     28    12     0    17    26      ∞
         *     10     ∞    17     0    15     13
         *      ∞    21    26    15     0     11
         *      ∞     ∞     ∞    13    11      0
         */
        System.out.println("插入顶点F,插入边(D,F,13)和(E,F,11)");
        int f_index = graph.insertVertex("F");
        //插入边(D,F,13)
        graph.insertEdge(3,f_index,13);
        //插入边(F,D,13)
        graph.insertEdge(new Triple(f_index,3,13));
        //插入边(E,F,11)
        graph.insertEdge(4,f_index,11);
        //插入边(F,E,11)
        graph.insertEdge(new Triple(f_index,4,11));
        System.out.println("带权无向图G3，" + graph.toString());

        System.out.println("深度优先遍历连通无向图G3:");
        for (int i = 0; i < graph.vertexCount(); i++)
            graph.DFSTraverse(i);

        System.out.println("广度优先遍历连通无向图G3:");
        for (int i = 0 ; i < graph.vertexCount() ; i++)
            graph.BFSTraverse(i);

        System.out.println();
        System.out.println("带权无向图G3，prim算法");
        graph.minSpanTree();

        System.out.println();
        System.out.println("带权无向图G3，Dijkstra算法");
        for(int i=0;i<graph.vertexCount();i++){
            graph.dijkstra(i);
        }

        System.out.println();
        System.out.println("带权有向图G3，Floyd算法，最短路径如下：");
        graph.floyd();
    }

    public MatrixGraph(int length) {
        this.vertexList = new SeqList<>(length);
        this.matrix = new int[length][length];
        initEgde();
    }

    public MatrixGraph(T[] vertices, Triple[] edges) {
        this.vertexList = new SeqList<>(vertices);
        this.matrix = new int[vertices.length][vertices.length];
        initEgde();

        for (Triple edge : edges) {
            this.insertEdge(edge);
        }
    }

    private void initEgde() {
        // 不同顶点之间的初始距离为无穷大，顶点和自身的距离为0
        int n = this.vertexList.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    this.matrix[i][j] = MAX_WEIGHT;
                }
            }
        }
    }

    public String toString() {
        String str = this.vertexList.toString() + "，邻接矩阵:  \n";
        int n = this.vertexList.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (this.matrix[i][j] == MAX_WEIGHT)
                    str += "     ∞";
                else str += String.format("%6d", this.matrix[i][j]);
            }
            str += "\n";
        }
        return str;
    }

    // 边 相关操作
    public void insertEdge(int i, int j, int weight) {
        if (i != j) {
            this.matrix[i][j] = weight;
        }
    }

    public void insertEdge(Triple edge) {
        this.insertEdge(edge.row, edge.column, edge.value);
    }

    public void removeEdge(int i, int j) {
        if (i != j) {
            this.matrix[i][j] = MAX_WEIGHT;
        }
    }

    public void removeEdge(Triple edge) {
        this.removeEdge(edge.row, edge.column);
    }

    public int weight(int i, int j) {
        return this.matrix[i][j];
    }

    // 顶点 相关操作
    //返回图的顶点数
    public int vertexCount() {
        return this.vertexList.size();
    }

    //返回顶点vi元素
    public T getVertex(int i) {
        return this.vertexList.get(i);
    }

    //设置顶点vi元素为x
    public void setVertex(int i, T x) {
        this.vertexList.set(i, x);
    }

    //插入元素为x的顶点，返回x顶点序号
    public int insertVertex(T x) {
        int[][] oldMatrix = this.matrix;

        // 添加顶点
        int ret = this.vertexList.insert(x);

        // 初始化邻接矩阵为默认值
        int vertexCount = this.vertexCount();
        this.matrix = new int[vertexCount][vertexCount];
        this.initEgde();

        // 根据之前的邻接矩阵，初始化边
        for (int i = 0; i < vertexCount - 1; i++) {
            for (int j = 0; j < vertexCount - 1; j++) {
                this.matrix[i][j] = oldMatrix[i][j];
            }
        }
        return ret;
    }

    //删除顶点vi及其所有关联的边
    public void removeVertex(int i) {
        int n = this.vertexCount();
        if (i >= 0 && i < n) {
            // 删除顶点
            this.vertexList.remove(i);

            //第i+1～n-1行元素上移一行，n为原顶点数
            for (int j = i + 1; j < n; j++)
                for (int k = 0; k < n; k++)
                    this.matrix[j - 1][k] = this.matrix[j][k];

            //第i+1～n-1列元素左移一列
            for (int k = i + 1; k < n; k++)
                for (int j = 0; j < n; j++)
                    this.matrix[j][k - 1] = this.matrix[j][k];
        } else throw new IndexOutOfBoundsException("i=" + i);
    }

    // 返回顶点vi在vj后的后继邻接顶点序号；
    // 若不存在后继邻接顶点，返回-1。
    private int next(int i, int j) {
        int n = this.vertexList.size();
        if (i >= 0 && i < n) {
            for (int k = j + 1; k < n; k++) {
                if (this.matrix[i][k] > 0 && this.matrix[i][k] < MAX_WEIGHT) {
                    return k;
                }
            }
        }
        return -1;
    }

    // 返回顶点vi的第一个邻接顶点序号
    // 若不存在，返回-1。
    private int first(int i) {
        int n = this.vertexList.size();
        if (i >= 0 && i < n) {
            for (int k = 0; k < n; k++) {
                if (this.matrix[i][k] > 0 && this.matrix[i][k] < MAX_WEIGHT) {
                    return k;
                }
            }
        }
        return -1;
    }

    //非连通图的一次深度优先搜索遍历, 从顶点Vi出发
    public void DFSTraverse(int i) {
        if(i<0 || i>=this.vertexCount())
            return;
        boolean[] visited = new boolean[this.vertexCount()];
        int j=i;
        do {
            if(!visited[j]){
                System.out.print("{ ");
                depthfs(j,visited);
                System.out.print("} ");
            }
            j = (j+1) % this.vertexCount();
        } while (j!=i);
        System.out.println();
    }

    //从顶点vi出发的一次深度优先搜索，遍历一个连通分量；visited指定访问标记数组。递归算法
    private void depthfs(int i, boolean[] visited) {
        System.out.print(this.vertexList.get(i) + " ");
        visited[i] = true;
        for(int j = next(i,-1);j!= -1 ; j=next(i,j))
            if(!visited[j])
                depthfs(j,visited);
    }

    //非连通图的一次广度优先搜索遍历，从顶点Vi出发
    public void BFSTraverse(int i) {
        if(i<0|| i>=this.vertexCount())
            return ;
        boolean[] visited = new boolean[this.vertexList.size()];
        Queue<Integer> que = new SeqQueue<Integer>(this.vertexCount()-1);
        int j = i;
        do {
            if (!visited[j]) {
                System.out.print("{ ");
                bfsTraverse(j, visited ,que);                     //从vj出发的一次广度优先搜索
                System.out.print("} ");
            }
            j = (j + 1) % this.vertexCount();                //在其他连通分量中寻找未被访问顶点
        } while (j != i);
        System.out.println();
    }

    //从顶点vi出发的一次广度优先搜索，遍历一个连通分量，使用队列
    private void bfsTraverse(int i, boolean[] visited,Queue<Integer> que) {
        System.out.print(this.vertexList.get(i) + " ");
        visited[i] = true;
        que.add(i);
        while(!que.isEmpty()){
            i = que.poll();
            for (int j = next(i,-1) ; j!= -1 ; j=next(i,j)){
                if(!visited[j]){
                    System.out.print(this.getVertex(j)+ " ");
                    visited[j] = true ;
                    que.add(j);
                }
            }
        }
    }

    //Prim算法，构造带权无向图的最小生成树，输出最小生成树的各边及代价
    //mst数组：表示从TV到V-TV的一条边
    public void minSpanTree() {
        // 初始化MST数组。从顶点v0出发，到其它点的权值
        Triple[] mst = new Triple[vertexCount() - 1];
        for (int i = 0; i < mst.length; i++) {
            mst[i] = new Triple(0, i + 1, this.weight(0, i + 1));
        }

        //选择n-1条边，每趟确定一条权值最小的边。
        //MST数组: 0~i是已加入到最小生成树的边TE，i+1~n-1是TV距离V-TV的最小权值
        for (int i = 0; i < mst.length; i++) {
            System.out.print("mst边集合：");
            for (int j = 0; j < mst.length; j++) {
                System.out.print(mst[j].toString() + ",");
            }
            System.out.println();

            //找到最小权值边的下标
            int min = i;
            for (int j = i + 1; j < mst.length; j++) {
                if (mst[j].value < mst[min].value) {
                    min = j;
                }
            }

            //将权值最小的边交换到第i个元素，表示该边加入TE集合
            Triple edge = mst[min];
            if (min != i) {
                mst[min] = mst[i];
                mst[i] = edge;
            }

            //将i+1～n-1的其他边用权值更小的边替换，即TV距离V-TV的最小权值
            int tv = edge.column;                          //刚并入TV的顶点
            for (int j = i + 1; j < mst.length; j++) {
                int v = mst[j].column;                     //原边在V-TV中的终点
                int weight = this.weight(tv, v);
                if (weight < mst[j].value)                   //若(tv,v)边比第j条边的权值更小，则替换
                    mst[j] = new Triple(tv, v, weight);
            }
        }

        // 打印结果
        System.out.print("\n最小生成树的边集合：");
        int mincost = 0;
        for (int i = 0; i < mst.length; i++) {
            System.out.print(mst[i] + " ");
            mincost += mst[i].value;
        }
        System.out.println("，最小代价为" + mincost);
    }

    //非负权值的单源最短路径（Dijkstra算法）
    //S：已确定最短路径集合
    //Path：最短路径终点的前一个顶点,如路径{A，D，C，E} 中的C
    //Dist：最短路径长度
    public void dijkstra(int i) {
        int n = this.vertexCount();             //图的顶点数
        boolean[] S = new boolean[n];           //已求出最短路径的顶点集合，初值全为false
        S[i] = true;                            //标记源点vi在集合S中。若i越界，Java抛出序号越界异常
        int[] dist = new int[n];                //最短路径长度
        int[] path = new int[n];                //最短路径终点的前一个顶点

        //初始化dist和path数组
        for (int j = 0; j < n; j++) {
            dist[j] = this.weight(i, j);
            path[j] = (j != i && dist[j] < MAX_WEIGHT) ? i : -1;
        }

        //寻找从vi到vj的最短路径，vj在V-S集合中
        for (int j = (i + 1) % n; j != i; j = (j + 1) % n) {
            //求路径长度最小值及其下标，确定一条最短路径的终点min并入集合S
            int mindist = MAX_WEIGHT, min = 0;
            for (int k = 0; k < n; k++) {
                if (!S[k] && dist[k] < mindist) {
                    mindist = dist[k];
                    min = k;
                }
            }
            //若没有其他最短路径则算法结束； 此语句对非连通图必需
            if (mindist == MAX_WEIGHT) {
                break;
            }
            S[min] = true;

            //调整从vi到V-S中其他顶点的最短路径及长度，更新dist、path
            for (int k = 0; k < n; k++) {
                if (!S[k] && this.weight(min, k) < MAX_WEIGHT
                        && dist[min] + this.weight(min, k) < dist[k]) {
                    dist[k] = dist[min] + this.weight(min, k);
                    path[k] = min;
                }
            }
        }

        System.out.print(this.getVertex(i) + "的单源最短路径：");
        for (int j = 0; j < n; j++)                            //输出顶点vi的单源最短路径
            if (j != i) {
                System.out.print(toPath(path, i, j) + "长度" + (dist[j] == MAX_WEIGHT ? "∞" : dist[j]) + "，");
            }
        System.out.println();
    }

    // 返回path路径数组中从顶点Vi到顶点Vj的一条路径字符串
    private String toPath(int[] path, int i, int j) {
        //路径单链表，记录最短路径经过的各顶点，用于反序
        LinkedList<T> pathLink = new LinkedList<T>();
        pathLink.insert(0, this.getVertex(j));     //终点Vj
        for (int k = path[j]; k != i && k != j && k != -1; k = path[k]) {
            pathLink.insert(0, this.getVertex(k)); //单链表头插入经过的顶点，反序
        }
        pathLink.insert(0, this.getVertex(i));     //起点vi
        return pathLink.toString();
    }

    //求带权图每对顶点间的最短路径及长度，Floyd算法
    public void floyd() {
        int n = this.vertexCount();                          //图的顶点数
        int[][] path = new int[n][n], dist = new int[n][n];     //最短路径及长度矩阵，初值为0
        for (int i = 0; i < n; i++)                            //初始化dist、path矩阵
            for (int j = 0; j < n; j++) {
                int w = this.weight(i, j);
                dist[i][j] = w;                           //dist初值是图的邻接矩阵
                path[i][j] = i != j && w < MAX_WEIGHT ? i : -1;
            }

        //以Vk作为其他路径的中间顶点
        for (int k = 0; k < n; k++) {
            //测试每对从Vi到Vj路径长度是否更短
            for (int i = 0; i < n; i++) {
                if (i != k) {
                    for (int j = 0; j < n; j++) {
                        if (j != k && j != i && dist[i][k] + dist[k][j] < dist[i][j]) {  //若更短，则替换
                            dist[i][j] = dist[i][k] + dist[k][j];
                            path[i][j] = path[k][j];
                        }
                    }
                }
            }
        }

        System.out.println("每对顶点间的最短路径如下：");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                if (i != j)
                    System.out.print(toPath(path[i], i, j) + "长度" + (dist[i][j] == MAX_WEIGHT ? "∞" : dist[i][j]) + "，");
            System.out.println();
        }
    }
}
